package com.yusong.algorithm.btree;


/**
 * 二分查找算法
 * https://time.geekbang.org/column/article/42520
 * 二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。
 */
public class BinarySearch {


    public static int baseSearch(int[] a, int value) {
        int low = 0;
        int high = a.length;
        while (low <= high){
            //位移运算提高性能：int mid = low + ((high - low) >> 1);
            int middle = low + (high - low)/2;

            if(value == a[middle]){
                return middle;
            }else if( value > a[middle]){
                low = middle + 1;
            }else {
                high = middle - 1;
            }
        }
        return -1;
    }


    /**
     * 变体一：查找第一个值等于给定值的元素
     * 有重复数据
     * 查找到了数据之后向左遍历还有没有一样的数据
     */
    public int firstSearch(int[] a, int value) {
        int low = 0;
        int high = a.length;
        int middle = low + ((high - low) >> 1);


        if(a[middle] == value){
            if(middle == 0 || a[middle -1] == value){
                high = middle - 1;
            }else {
                return middle;
            }
        }

        return -1;
    }


    /**
     * 变体二：查找最后一个值等于给定值的元素
     * 有重复数据
     * 查找到了数据之后向右遍历还有没有一样的数据
     */
    public int lastSearch(int[] a, int n, int value) {


        return -1;
    }


    /**
     * 变体三: 找到第一个大于该值的值
     * 我的思路:完整的二分查找
     * 思路2:第一个大于转化为两个相邻元素的约束
     */
    public int firstHighSearch(int[] a, int value) {
        int low = 0;
        int high = a.length;
        if(high <= value){
            return -1;
        }
        int firstHigh = high;

        int middle = low + ((high - low) >> 1);

        if(a[middle] > value){
            firstHigh = middle;
            high = middle -1;
        }else {

            low = middle +1;
        }

        return firstHigh;
    }


    /**
     * IP查找
     * 1.排序：我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。
     */


    /**
     * test
     */
    public static void main(String[] args){
        int data[] = {1, 2, 4,9, 10, 11, 17,17,17, 32, 100, 130};
        System.out.println(baseSearch(data, 11));

    }



}
